#include <IndexedSet.hpp>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void * AllocAlign( const uint64_t numBytes, const char * memname ) {
    void * tmp = NULL;

    uint32_t rc;
    rc = posix_memalign( &tmp, lineSize, numBytes );        
    const bool alloc_failed = rc != 0;
    
    if( alloc_failed ) {
        fflush( stderr );
        fflush( stdout );
        fprintf( stderr, "------------------------------------------------\n" );
        fprintf( stderr, "posix_memalign() failed\n" );
        fprintf( stderr, "... memname = %s\n", memname );
        fprintf( stderr, "... asked for %" U64CHAR " bytes\n", numBytes );
        fprintf( stderr, "------------------------------------------------\n" );
        fflush( stderr );
        fflush( stdout );
        assert( false );
    }
    else {
        #ifdef __FIS_DEBUG_COMPILE__
        fflush( stderr );
        fflush( stdout );
        fprintf( stderr, "------------------------------------------------\n" );
        fprintf( stderr, "AllocAlign() success!\n" );
        fprintf( stderr, "... memname = %s\n", memname );
        fprintf( stderr, "... asked for %" U64CHAR " bytes\n", numBytes );
        fprintf( stderr, "------------------------------------------------\n" );
        fflush( stderr );
        fflush( stdout );
        #endif
    }
    return tmp;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void IndexedSet::LockEveryBucket( void ) const {
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        LOCK_FUNC( &locks[ bucketIdx ] );
    }
}
void IndexedSet::UnlockEveryBucket( void ) const {
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        UNLOCK_FUNC( &locks[ bucketIdx ] );
    }
}
void IndexedSet::PrintBucketStats( void ) const {
    #ifdef __FIS_DEBUG_COMPILE__

    double avg = BucketOccupancyAverage();
    double dev = BucketOccupancyStdDev( avg );
    
    cout << "avg = " << avg << endl;
    cout << "dev = " << dev << endl;
    #endif
}
double IndexedSet::BucketOccupancyAverage( void ) const {

    #ifdef __FIS_DEBUG_COMPILE__
    LockEveryBucket();
    
    uint64_t totalOcc = 0ULL;
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        totalOcc += CountBucketOccupancy( bucketIdx );
    }
    
    UnlockEveryBucket();
    assert( totalOcc == numEntries );
    #endif
    
    double avg = double( numEntries ) / double( numBuckets );
    return avg;
}
double IndexedSet::BucketOccupancyStdDev( double avg ) const {
    
    double d2sum = OccAvgDeltaSqSum( avg );        
    double dev = sqrt( d2sum / double( numBuckets ) );
    return dev;
}
double IndexedSet::OccAvgDeltaSqSum( double avg ) const {
    
    double d2sum = 0.0;
    
    LockEveryBucket();
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        #ifdef __FIS_BUCKET_STATS__
        double delta = avg - load[ bucketIdx ];
        #else
        double delta = avg - double( CountBucketOccupancy( bucketIdx ) );
        #endif
        d2sum += ( delta * delta );
    }
    UnlockEveryBucket();
    return d2sum;
}
uint32_t IndexedSet::BucketOccupancyMinimum ( void ) const {
    
    uint32_t min = 0xFFFFFFFF;
    
    LockEveryBucket();
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        #ifdef __FIS_BUCKET_STATS__
        min = MIN( min, load[ bucketIdx ] );
        #else
        min = MIN( min, CountBucketOccupancy( bucketIdx ) );
        #endif
    }
    UnlockEveryBucket();
    return min;        
}
double IndexedSet::Load( void ) const {
    const double n = double( numEntries );
    const double t = double( numBuckets ) * double( keysPerBucket );
    return n / t;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void IndexedSet::FreeKeysAndSigs( void ) {
    FREE( keys );
    FREE( sigs );
}
void IndexedSet::init( void ) {
    preLoad = 0;
    numEntries = 0;
    name  = NULL;
    keys  = NULL;
    sigs  = NULL;
    load  = NULL;
    locks = NULL;
    
    const uint64_t totalKeyBytes  = uint64_t( numKeys    ) * uint64_t( bytesPerKey );
    const uint64_t totalSigBytes  = uint64_t( numBuckets ) * uint64_t( lineSize    );
    const uint64_t totalLockBytes = uint64_t( numBuckets ) * uint64_t( sizeof( fis_lock_t ) );
    keys = ( uint64_t * ) AllocAlign( totalKeyBytes, "keys" );
    sigs = ( uint64_t * ) AllocAlign( totalSigBytes, "sigs" );
    locks = ( fis_lock_t * ) AllocAlign( totalLockBytes, "locks" );
    
    memset( keys, 0, totalKeyBytes );
    memset( sigs, 0, totalSigBytes );
    
    for( uint32_t i = 0; i < numBuckets; i++ ) {
        LOCK_INIT_FUNC( &locks[i], NULL );
    }
    LOCK_INIT_FUNC( &glock, NULL );
    
    assert(  keys != NULL );
    assert(  sigs != NULL );        
    assert( locks != NULL );
    
    #ifdef __FIS_DEBUG_COMPILE__
    info( "FastIndexedSet():" );
    info( "wordsPerBucket = %d", wordsPerBucket );
    info( "keysPerBucket  = %d", keysPerBucket  );
    info( "wordsPerKey    = %d", wordsPerKey    );        
    max_sig_line = (LSU*) &sigs[ SigOffset( numBuckets ) ];
    #endif
    #ifdef  __FIS_BUCKET_STATS__
    const uint64_t totalLoadBytes = uint64_t( numBuckets ) * uint64_t( sizeof( uint32_t ) );
    load = ( uint32_t * ) AllocAlign( totalLoadBytes, "load" );
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        load[ bucketIdx ] = 0;
    }
    #endif
}
IndexedSet::IndexedSet( const uint32_t _idxBits, const uint32_t _wordsPerKey ) :
    idxBits        ( _idxBits     ),
    wordsPerKey    ( _wordsPerKey ),
    bytesPerKey    ( wordsPerKey * sizeof( uint64_t ) ),
    bytesPerBucket ( bytesPerKey * keysPerBucket ),
    wordsPerBucket ( bytesPerBucket / sizeof( uint64_t ) ),
    numBuckets     ( 1 << idxBits ),
    hashMask       ( uint64_t( numBuckets ) - 1ULL ),
    numKeys        ( keysPerBucket * numBuckets )
{
    init();
}
IndexedSet::~IndexedSet( void ) {
    #ifdef __FIS_DEBUG_COMPILE__
    cout << "~IndexedSet(): " << name  << endl;
    #endif
    
    FREE( keys );
    FREE( sigs );
    FREE( name );
    FREE( load );
    FREE( locks );
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void IndexedSetBase::SetHash( HashWrapper * _hf ) {
    #ifdef __FIS_DEBUG_COMPILE__
    info( "FastIndexedSetBase::SetHash(): name = %s", name );
    #endif
    hf = _hf;
}
void IndexedSetBase::SetName( const char * _name ) {
    if( name ) {
        FREE( name );
    }
    const uint32_t nameLen = strlen( _name );
    name = NULL;
    name = (char *) CALLOC( nameLen + 1, sizeof( char ) );
    assert( name );
    strcpy( name, _name );
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
IndexedCounters::IndexedCounters( const uint32_t _idxBits, const uint32_t _wordsPerKey, const uint64_t _seed ) :
    IndexedSet( _idxBits, _wordsPerKey ),
    topOfDedupIdx( NumAllocatableKeys() - 1 )
{
    a_totals = 0ULL;
    k_totals = 0ULL;
    u_totals = 0ULL;
    a_unique = 0ULL;
    k_unique = 0ULL;
    u_unique = 0ULL;
    a_counts = NULL;
    k_counts = NULL;
    u_counts = NULL;
    numEntries = 0ULL;
    const uint64_t totalValBytes  = uint64_t( numKeys ) * uint64_t( bytesPerVal );
    a_counts = ( uint32_t * ) AllocAlign( totalValBytes, "all_mem reference counts" );
    k_counts = ( uint32_t * ) AllocAlign( totalValBytes, "kernmem reference counts" );
    u_counts = ( uint32_t * ) AllocAlign( totalValBytes, "usermem reference counts" );
    assert( a_counts != NULL );
    assert( k_counts != NULL );
    assert( u_counts != NULL );
    memset( a_counts, 0, totalValBytes );
    memset( k_counts, 0, totalValBytes );
    memset( u_counts, 0, totalValBytes );
            
    topOfOverflowIdx = NumAllocatableKeys();

    #ifdef __FIS_DEBUG_COMPILE__
    cout << "IndexedCounters::IndexedCounters(): topOfDedupIdx = " << topOfDedupIdx << endl;
    #endif
}
IndexedCounters::~IndexedCounters( void ) {
    #ifdef __FIS_DEBUG_COMPILE__
    cout << "IndexedCounters::~IndexedCounters(): " << name << endl;
    #endif
    FREE( a_counts );
    FREE( k_counts );
    FREE( u_counts );
}
void IndexedCounters::Audit( void ) const {
}
void IndexedCounters::Clear( void ) {
    assert( a_counts != NULL );
    assert( k_counts != NULL );
    assert( u_counts != NULL );

    const uint64_t totalValBytes  = uint64_t( numKeys ) * uint64_t( bytesPerVal );
    const uint64_t totalKeyBytes  = uint64_t( numKeys    ) * uint64_t( bytesPerKey );
    const uint64_t totalSigBytes  = uint64_t( numBuckets ) * uint64_t( lineSize    );

    memset( a_counts, 0, totalValBytes );
    memset( k_counts, 0, totalValBytes );
    memset( u_counts, 0, totalValBytes );
    memset( keys, 0, totalKeyBytes );
    memset( sigs, 0, totalSigBytes );
    for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {
        load[ bucketIdx ] = 0;
    }    
}
void IndexedCounters::AccumCounts( void ) {
    a_unique = 0ULL;
    k_unique = 0ULL;
    u_unique = 0ULL;
    a_totals = 0ULL;
    k_totals = 0ULL;
    u_totals = 0ULL;
    
    uint32_t * pa = a_counts;
    uint32_t * pk = k_counts;
    uint32_t * pu = u_counts;
    
    for( uint32_t keyIdx = 0; keyIdx < numKeys; keyIdx++ ) {
        const uint64_t a = uint64_t( *pa ); pa++;
        const uint64_t k = uint64_t( *pk ); pk++;
        const uint64_t u = uint64_t( *pu ); pu++;
        
        if( a ) {
            a_unique++;
            a_totals += a;
        }
        if( k ) {
            k_unique++;
            k_totals += k;
        }
        if( u ) {
            u_unique++;
            u_totals += u;
        }
    }
}
void IndexedCounters::BuildRCHisto( map< uint64_t, uint64_t > & rchisto ) const {

    uint32_t * c = &a_counts[0];

    for( uint32_t i = 0; i < numKeys; i++ ) {
        const uint64_t count = uint64_t( *c );
        c++;
        
        if( count ) {
            rchisto[ count ]++;
        }
    }
}
uint64_t IndexedCounters::size( void ) const {
    #ifdef __FIS_INLINE_COUNTS__
    return uint64_t( numEntries );
    #else
    return a_unique;
    #endif
}
uint32_t IndexedCounters::InsertKey( const uint64_t * k ) {
    const uint64_t h = hf->hash( k, wordsPerKey );
    const uint32_t bucketIdx = hashMask & h;
    const unsigned char sig  = h2sig( h );

    uint32_t keyIndex = FindKey( k, bucketIdx, sig );
    if( IsInvalidIdx( keyIndex ) ) {
        
        if( BucketLoad( bucketIdx ) == maxLoad ) {
            // no room to insert:
            // ... return invalid index
            return IDX_NOT_FOUND_VAL;
        }
        else {
            keyIndex = KeyNotFoundInsertKey( k, bucketIdx, sig );
            #ifdef __FIS_INLINE_COUNTS__
            __sync_fetch_and_add( &numEntries, 1 );
            #endif
        }
    }
    
    return keyIndex;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void DleftIndexedCounters::Audit( void ) const {
    l->Audit();
    r->Audit();
}
void DleftIndexedCounters::FreeKeysAndSigs( void ) {
    l->FreeKeysAndSigs();
    r->FreeKeysAndSigs();
}
void DleftIndexedCounters::BuildRCHisto( map< uint64_t, uint64_t > & rchisto ) const {
    
    l->BuildRCHisto( rchisto );
    r->BuildRCHisto( rchisto );
    
    for( map< multi_word, uint64_t >::const_iterator it = a_over_uniq.begin(); it != a_over_uniq.end(); it++ ) {
        uint64_t count = it->second;
        rchisto[ count ]++;
    }
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
DleftIndexedCounters::DleftIndexedCounters( const uint32_t _idxBits, const uint32_t _wordsPerKey ) :
    idxBits     ( _idxBits ),
    wordsPerKey ( _wordsPerKey ),
    numBuckets  ( 1 << idxBits ),
    hashMask    ( uint64_t( numBuckets ) - 1ULL )
{
    a_over_total = 0ULL;
    k_over_total = 0ULL;
    u_over_total = 0ULL;
    name  = NULL;
    
    l = new IndexedCounters( ( idxBits - 1 ), wordsPerKey );
    r = new IndexedCounters( ( idxBits - 1 ), wordsPerKey );
    assert( l );
    assert( r );
    base_l = l;
    base_r = r;

    keyIdxOffset = l->NumAllocatableKeys();
    LOCK_INIT_FUNC( &glock, NULL );
}
DleftIndexedCounters::~DleftIndexedCounters( void ) {
    #ifdef __FIS_DEBUG_COMPILE__
    cout << "~DleftIndexedCounters(): " << name << endl;
    #endif
    delete l;
    delete r;
}
void DleftIndexedCounters::IncCountByKeyOverflow( const uint64_t * k, const uint32_t arc, const uint32_t krc, const uint32_t urc ) {

    Lock();
    
    multi_word key( wordsPerKey, k );

    if( arc ) {
        a_over_uniq[ key ] += arc;
        a_over_total += arc;
    }
    if( krc ) {
        k_over_uniq[ key ] += krc;
        k_over_total += krc;
    }
    if( urc ) {
        u_over_uniq[ key ] += urc;
        u_over_total += urc;
    }
    
    Unlock();
}
uint32_t DleftIndexedCounters::InsertKey( const uint64_t * k ) {

    uint32_t keyIdx = 0xFFFFFFFF;

    const bool exists_l = l->KeyExists( k );
    if( exists_l ) {
        keyIdx = l->InsertKey( k );
    }
    else {
        const bool exists_r = r->KeyExists( k );
        
        if( exists_r ) {
            keyIdx = r->InsertKey( k );
            keyIdx += keyIdxOffset;
        }
        else {
            const uint32_t lbi = l->LockBucket( k );
            const uint32_t rbi = r->LockBucket( k );
            
            const bool exists_l_locked = l->KeyExists( k );
            const bool exists_r_locked = r->KeyExists( k );
            const bool does_not_exist = (!exists_l_locked) && (!exists_r_locked);
            
            if( does_not_exist ) {
                // allocate:
                // ... should be the common case here
                const uint32_t load_l = l->BucketLoad( k );
                const uint32_t load_r = r->BucketLoad( k );
                
                if( load_l < load_r ) {
                    keyIdx = l->InsertKey( k );
                }
                else if( load_r < load_l ) {
                    keyIdx = r->InsertKey( k );
                    keyIdx += keyIdxOffset;
                }
                else {
                    assert( load_l == load_r );
                    
                    if( load_r == r->MaxLoad() ) {
                        // overflow:
                        // ... indicated by key index > size of both tables
                        keyIdx = keyIdxOffset + keyIdxOffset;
                    }
                    else {
                        // tie breaker goes left!
                        keyIdx = l->InsertKey( k );
                    }
                }
            }
            else {
                // someone else allocated before we could grab the lock:
                // ... sanity check: should not exist in both
                // ... sanity check: and should exist in at least one
                const bool exists_both = exists_l_locked && exists_r_locked;
                const bool exists_in_1 = exists_l_locked || exists_r_locked;
                
                assert( !exists_both );
                assert(  exists_in_1 );
                
                if( exists_l_locked ) {
                    keyIdx = l->InsertKey( k );
                }
                if( exists_r_locked ) {
                    keyIdx = r->InsertKey( k );
                    keyIdx += keyIdxOffset;
                }
            }
            l->UnlockBucket( lbi );
            r->UnlockBucket( rbi );
        }
    }
    DEBUG_ASSERT( keyIdx != 0xFFFFFFFF );
    return keyIdx;
}
void DleftIndexedCounters::IncCountByKey( const uint64_t * k, const uint32_t arc, const uint32_t krc, const uint32_t urc ) {

    uint32_t keyIndex = InsertKey( k );

    if( keyIndex < keyIdxOffset ) {
        // left
        l->IncCountByIndex( keyIndex, arc, krc, urc );
    }
    else {
        keyIndex -= keyIdxOffset;
        if( keyIndex < keyIdxOffset ) {
            // right
            r->IncCountByIndex( keyIndex, arc, krc, urc );
        }
        else{
            // overflow
            IncCountByKeyOverflow( k, arc, krc, urc );
        }
    }
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void DleftIndexedCounters::AccumCounts( void ) {
    l->AccumCounts();
    r->AccumCounts();
    a_totals = l->ATotals() + r->ATotals() + a_over_total;
    k_totals = l->KTotals() + r->KTotals() + k_over_total;
    u_totals = l->UTotals() + r->UTotals() + u_over_total;
    a_unique = l->AUnique() + r->AUnique() + a_over_uniq.size();
    k_unique = l->KUnique() + r->KUnique() + k_over_uniq.size();
    u_unique = l->UUnique() + r->UUnique() + u_over_uniq.size();
    
}
double DleftIndexedCounters::Load( void ) const {
    const double lload = l->Load();
    const double rload = r->Load();
    
    const double ratio = rload / lload;
    if( ratio > 1.0 ) {
        printf( "Load error: ratio = %f\n", ratio );
    }
    if( ratio < 0.8 ) {
        printf( "Load error: ratio = %f\n", ratio );
    }
    
    return 0.5 * ( lload + rload );
}




